package math;

/**
 * 约瑟夫环（约瑟夫问题）是一个数学的应用问题：
 * 已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. 从编号为 k 的人开始报数，数到 m 的那个人出圈；
 * 他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。
 * <p>
 * 例如：有10个人围成一圈进行此游戏，每个人编号为 1-10 。. 若规定数到 3 的人出圈。. 则游戏过程如下。.
 * （1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。. 1， 2， 【 3 】， 4， 5， 6， 7， 8， 9， 10。.
 * （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。.
 *
 * @author Liaorun
 */
public class JosephusProblem {


    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = head;

        System.out.println(josephusKill1(head, 3).value);
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node josephusKill1(Node head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }

        Node last = head;
        while (last.next != head) {
            last = last.next;
        }
        int count = 0;
        while (head != last) {
            if (++count == m) {
                last.next = head.next;
                count = 0;
            } else {
                last = last.next;
            }

            head = last.next;
        }

        return head;
    }

    public static Node josephusKill2(Node head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }

        Node cur = head.next;
        // list size
        int temp = 1;

        while (cur != head) {
            temp++;
            cur = cur.next;
        }

        temp = getLive(temp, m);
        while (--temp != 0) {
            head = head.next;
        }

        head.next = head;

        return head;
    }

    /**
     * 现在一个有i个节点，数到m就杀死节点，最终会活下一个节点，
     * 请返回开始有i个节点时候这个活着节点的编号
     *
     * @param i 节点数量
     * @param m 第几个死
     * @return 最后活着的节点
     */
    private static int getLive(int i, int m) {
        // base case 只有一个节点的情况
        if (i == 1) {
            return 1;
        }

        // 老节点编号 = （新节点编号 + m - 1) % i + 1
        return (getLive(i - 1, m) + m - 1) % i + 1;
    }

    /**
     * 长度为i-1的情况下，编号为x,返回同一个节点，杀之前的编号
     * <p>
     * a = getNo(1,2,m);
     * b = getNo(a,3,m);
     * c = getNo(b,4,m);
     *
     * @param x
     * @param i
     * @param m
     * @return
     */
    public static int getNo(int x, int i, int m) {
        return (x + m - 1) % i + 1;
    }

    /**
     * 0..n-1 围成一个圈，
     * 杀n-1轮，返回活着的人的原始下标
     *
     * @param n
     * @param arr
     * @return
     */
    public static int live(int n, int[] arr) {
        return oldNo(n, arr, 0);
    }

    /**
     * 还剩i个人，当前取用的数字是arr[index],并且下面的过程，从index出发，循环取用
     * 返回那个人会活
     *
     * @param i     还剩的人数
     * @param arr   所有人持有的号码
     * @param index 人的下标
     * @return
     */
    public static int oldNo(int i, int[] arr, int index) {
        if (i == 1) {
            return 1;
        }
        // 老节点编号 = （新节点编号 + m - 1) % i + 1
        return (oldNo(i - 1, arr, nextIndex(arr.length, index)) + arr[index] - 1) % i + 1;
    }

    private static int nextIndex(int length, int index) {
        return index == length - 1 ? 0 : index + 1;
    }


    public static void printCircularList(Node head) {
        if (head == null) {
            return;
        }

        System.out.println("Circular List: " + head.value + " ");
        Node cur = head.next;

        while (cur != head) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }

        System.out.println("-> " + head.value);
    }
}
